package leetcode.hot100;

import java.util.HashMap;

@SuppressWarnings("all")
public class _208_实现Trie {

    private final Node root = new Node();

    /**
     * 初始化前缀树对象
     */
    public _208_实现Trie() {
    }

    /**
     * 向前缀树中插入字符串 word
     */
    public void insert(String word) {
        checkKey(word);

        Node node = root;
        int len = word.length();
        for (int i = 0; i < len; i++) {
            char c = word.charAt(i);
            Node child = node.getChildren().get(c);
            if (child == null) {
                // 新增结点
                child = new Node();
                node.getChildren().put(c, child);
            }
            // 不论新增与否都要向下一层结点查找
            node = child;
        }
        node.isEnd = true;
    }

    /**
     * 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false
     */
    public boolean search(String word) {
        checkKey(word);
        Node node = getNode(word);
        return node != null && node.isEnd;
    }

    /**
     * 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false
     */
    public boolean startsWith(String prefix) {
        checkKey(prefix);
        return getNode(prefix) != null;
    }

    private Node getNode(String str) {
        checkKey(str);

        int len = str.length();
        Node node = root;
        for (int i = 0; i < len; i++) {
            // 循环取出每一个字符
            char c = str.charAt(i);
            // 判断该字符是否存在当前结点的子结点中
            node = node.getChildren().get(c);
            if (node == null) return null;
        }
        return node;
    }

    private void checkKey(String key) {
        if (key == null || key.length() == 0) {
            throw new IllegalArgumentException("参数不能为空");
        }
    }

    private static class Node {
        boolean isEnd;
        HashMap<Character, Node> children;

        // 保证存储子结点的哈希表不为空，可以减少很多判断
        public HashMap<Character, Node> getChildren() {
            return children != null ? children : (children = new HashMap<>());
        }
    }
}
